/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>

using namespace std;

#define INT_MAX 20

typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus; 
typedef enum { UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD } EStatus; 

template <typename Tv, typename Te> 
class Graph { 
private:
   void reset() { 
      for (int i = 0; i < n; i++) { 
         status(i) = UNDISCOVERED; dTime(i) = fTime(i) = -1; 
         parent(i) = -1; priority(i) = INT_MAX; 
         for (int j = 0; j < n; j++) 
            if (exists(i, j)) status(i, j) = UNDETERMINED; 
      }
   }
   void BFS(int, int&); 
   void DFS(int, int&); 
   void BCC(int, int&, stack<int>&); 
   bool TSort(int, int&, stack<Tv>*); 
   template <typename PU> void PFS(int, PU); 
public:

   int n; 
   virtual int insert(Tv const &) = 0; 
   virtual Tv remove(int) = 0; 
   virtual Tv& vertex(int) = 0; 
   virtual int inDegree(int) = 0; 
   virtual int outDegree(int) = 0; 
   virtual int firstNbr(int) = 0; 
   virtual int nextNbr(int, int) = 0; 
   virtual VStatus& status(int) = 0; 
   virtual int& dTime(int) = 0; 
   virtual int& fTime(int) = 0; 
   virtual int& parent(int) = 0; 
   virtual int& priority(int) = 0; 

   int e; 
   virtual bool exists(int, int) = 0; 
   virtual void insert(Te const &, int, int, int) = 0; 
   virtual Te remove(int, int) = 0; 
   virtual EStatus& status(int, int) = 0; 
   virtual Te& edge(int, int) = 0; 
   virtual int& weight(int, int) = 0; 

   void bfs(int); 
   void dfs(int); 
   void bcc(int); 
   stack<Tv>* tSort(int); 
   void prim(int); 
   void dijkstra(int); 
   template <typename PU> void pfs(int, PU); 
};


#include "Graph_implementation.h"
